package Offer;

/*
*   剑指 Offer 26. 树的子结构
    输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
    B是A的子结构， 即 A中有出现和B相同的结构和节点值。
* */

import org.junit.Test;

/*
    (约定空树不是任意一个树的子结构)
    思路：
        先判断B的根节点是否在A中,然后依次比较左右子孙结点
        定位B根节点是否在A中的方法是采用先序、中序、后序或层序遍历（使用队列来实现）中的一种
* */
public class T26_isSubStructure {
    @Test
    public void test() {
        /*
            [4,2,3,4,5,6,7,8,9]
            [4,8,9]


            [10,12,6,8,3,11]
            [10,12,6,8]

            [3,5,0,3,4]
            [1,-4,2,-1,3,-3,-4,0,-3,-1]

        */

        TreeNode  A = new TreeNode(10);
        TreeNode A1 = new TreeNode(12);
        TreeNode A2 = new TreeNode(6);
        TreeNode A3 = new TreeNode(8);
        TreeNode A4 = new TreeNode(3);
        TreeNode A5 = new TreeNode(11);

        A.left = A1;
        A.right = A2;

        A1.left = A3;
        A1.right = A4;

        A2.left = A5;


        TreeNode B = new TreeNode(10);
        TreeNode B1 = new TreeNode(12);
        TreeNode B2 = new TreeNode(6);
        TreeNode B3 = new TreeNode(8);

        B.left = B1;
        B.right = B2;

        B1.left = B3;

        System.out.println(isSubStructure(A, B));

    }

    /*public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) {
            return false;
        }

        TreeNode tmp = preorder(A, B);//这一步没必要，导致效率很低 //先序遍历定位结点（A中可能存在多个同B的结点）
        boolean flag = check(tmp, B);
        if (flag) {
            return true;
        }

        //递归左右子树(这样就不会漏)
        return isSubStructure(A.left, B)|| isSubStructure(A.right, B);
    }*/

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) {
            return false;
        }

        boolean flag = check(A, B);
        if (flag) {
            return true;
        }

        //递归左右子树(这样就不会漏)
        return isSubStructure(A.left, B)|| isSubStructure(A.right, B);
    }

    /**
     * 具有相同的根节点，判断两个树是否相同
     * @param A
     * @param B
     * @return
     */
    boolean check(TreeNode A, TreeNode B) {
        if (A == null && B == null) { //树节点都为空
            return true;
        }

//        如果成立说明 B != null
        if (A == null) { //其中一个树结点为空
            return false;
        }

//       如果成立说明 A != null
        if (B == null) { //其中一个树结点为空
            return true;
        }

        if (A.val == B.val) { //根结点相同
            // 递归左右孩子
            return check(A.left, B.left) && check(A.right, B.right);
        }else{
            //根节点不同，直接返回即可
            return false;
        }
    }
    /**
     * 先序遍历 根 左 右
     * 通过遍历A找B的根结点
     * @param A
     * @param B
     * @return 如果没有找到返回null，找到了返回该结点在树A中的位置
     * 其实这里感觉preorder()和check()有重复的地方，只需写check()即可！因为它里面也是先序遍历来的
     */
//    TreeNode preorder(TreeNode A, TreeNode B) {
//        if (A == null||B==null)
//            return null;
//
//        if (A.val == B.val) {
//            return A;
//        }
//
//        //找左边
//        TreeNode left = preorder(A.left, B);
//        if (left != null) {
//            return left;
//        }
//
//        //左边没有找右边
//        TreeNode right = preorder(A.right, B);
//        if (right != null) {
//            return right;
//        }
//        return null;
//    }





    //大佬的答案
    public boolean isSubStructure1(TreeNode A, TreeNode B) {
        return (A != null && B != null) &&
                (recur(A, B) || isSubStructure1(A.left, B) || isSubStructure1(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null)
            return true;//第一次调用recur的时候,B!=null,所以当B为null的时候说明B树已经遍历到尽头了
        if(A == null || A.val != B.val)
            return false;

        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}
